Error correction encoding technologies achieving large coding gain have been introduced to satellite communications and mobile telecommunication systems in order to meet the demands regarding the system structure such as reducing required power and the size of antennas. A low-density parity-check code is known as an error correction code achieving very large coding gain, and has been used in various communication systems and storage units such as magnetic storage units.
The low density parity check code does not refer to one particular error correction encoding method, but it is a general term for error correction codes characterized by a sparse check matrix (most elements in the matrix are 0, and the number of “1” elements is very few). By selecting a sparse check matrix and using an iterative decoding method such as the sum-product algorithm, the low-density parity-check code can realize an error correction encoding system capable of achieving very large coding gain close to the theoretical limit (for instance refer to Non-Patent Documents 1 and 2).
Technical problems regarding the low-density parity-check code are as follows. The amount of calculation required for the encoding method (the method for calculating a redundant bit sequence from an information bit sequence) is large, and it is difficult to evaluate the performance of the error-rate characteristics (the obtained coding gain) in an area where the error probability is low, particularly an error floor area. In a most typical encoding apparatus in which the encoding system is constituted by matrix multiplication by a generator matrix of the code, the number of exclusive-OR operations required is proportional to the square of the code length.
Further, when an encoding apparatus is constituted by a check matrix of the code, the check matrix is transformed by means of elementary matrix transformations so that it partially forms a diagonal matrix such as an expression (1) and the apparatus is realized by the transformed check matrix.
                    [                  Expression          ⁢                                          ⁢          1                ]                                                            [                  A          |                                                    1                                                                                                                                                                                                        0                                                                                                                                                  1                                                                                                                                                                                                                                                                                                                                                                                            ⋱                                                                                                                                                  0                                                                                                                                                                                                        1                                                    ]                            (        1        )            
More concretely, when the part indicated by A in the expression (1) is an r×k matrix (where r and k represent positive integers), and c1, c2, . . . , ck is an information bit series of k bits, each bit pi (where i represents an integer between 1 and r inclusive) of a redundant bit string p1, p2, . . . , pr of r bits that corresponds to the information bit series of k bits can be derived by the following expression (2):
                    [                  Expression          ⁢                                          ⁢          2                ]                                                                      p          i                =                                            ∑                              j                =                1                            k                        ⁢                                          a                                  i                  ,                  j                                            ⁢                              c                j                                              =                                                    a                                  i                  ,                  1                                            ⁢                              c                1                                      +                                          a                                  i                  ,                  2                                            ⁢                              c                2                                      +            …            +                                          a                                  i                  ,                  k                                            ⁢                              c                k                                                                        (        2        )            
Here, ai, j in the expression (2) represents the (i, j) element of the r×k matrix A (where i represents an integer between 1 and r inclusive, and j represents an integer between 1 and k inclusive). Therefore, in order to constitute an encoding apparatus of an error correction code, the r×k matrix A is held in a storage unit such as a memory, and exclusive-OR operations need to be performed as many times as the number of “1”s in the elements of the matrix.
FIG. 7 shows an example of a conventional encoding apparatus relating to the low-density parity-check code. 51 in FIG. 7 is a redundant bit string calculating unit that performs the expression (2), 52 in FIG. 7 is a memory that holds the matrix A in the expression (1), and 53 in FIG. 7 is a switch.
In regard to the reduction of storage units and exclusive-OR units in an encoding apparatus, a method in which the amount of memory is reduced and exclusive-OR operations are simplified by limiting the check matrix to a matrix constituted by a cyclic permutation matrix in the block-matrix form and imposing regularity on the matrix A (for instance refer to Patent Document 1), and a method for constituting low-density parity-check codes in which the number of “1”s in the elements of the matrix A is minimized whereas the coding gain obtained by iterative decoding is maximized (for instance refer to Non-Patent Document 3) are known.
Further, as error correction codes with which an encoding apparatus can easily be realized, cyclic codes in which a redundant bit string is calculated by using only a polynomial dividing circuit are known; the cyclic codes are represented by Reed Solomon (RS) code and BCH code, in particular. Further, as with the aforementioned cyclic codes, an encoding apparatus can easily be realized by using convolutional codes.
However, in the cyclic codes or the convolutional codes having a long constraint length, the amount of calculation required for soft-decision decoding that performs decoding with a close-to-optimum precision is very large, offering a problem, and sufficient coding gain cannot obtained, compared with the low-density parity-check codes in which decoding can easily be performed with a close-to-optimum precision using an iterative decoding unit utilizing the aforementioned sum-product algorithm, which is courted as a problem. As relatively simple codes that can be decoded with a close-to-optimum precision using an iterative decoding and used for an encoding apparatus, turbo codes (for instance, refer to Patent Document 2) are known, however, the turbo codes have low code rates (the ratio between the lengths of the information bit string and the code bit string), therefore they are not suitable for a system that requires a high code rate.
The fact that the evaluation of the error-rate characteristics of the low-density parity-check codes and the performance prediction of the error-rate characteristics can be generally performed by a system called “density evolution” in an area where the error probability is sufficiently high is known (for instance, refer to Non-Patent Document 4). The performance prediction of the error-rate characteristics in an area where the error probability is low, particularly in an area called error floor, is evaluated by an experimental method utilizing a computer simulation.
As described above, the conventional encoding apparatus relating to a low-density parity-check code are implemented by the storage units that hold the matrix A in the expression (1) and the operation processing units that perform the operation of the expression (2). Further, the evaluation of the error-rate characteristics is performed experimentally.
[Patent Document 1]
Japanese Patent Kokai Publication No. JP-P2003-115768A (pp. 10-11, FIGS. 4 to 7)
[Patent Document 2]
U.S. Pat. No. 5,446,747 (p. 2, FIG. 1)
[Non-Patent Document 1]
Gallager, R., “Low-Density Parity-Check Codes,” MIT Press, 1963
[Non-Patent Document 2]
MacKay, D. J. C., “Good Error-Correcting Codes Based on Very Sparse Matrices,” IEEE Transactions on Information Theory, Vol. 45, No. 2, March 1999, pp. 399-431
[Non-Patent Document 3]
Richardson, T. J., and Urbanke, R. L., “Efficient Encoding of Low-Density Parity-Check Codes,” IEEE Transactions on Information Theory, Vol. 47, No. 2, February 2001, pp. 638-656 [Non-Patent Document 4]
Richardson, T. J., Shokrollahi, M. A. and Urbanke, R. L., “Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes,” IEEE Transactions on Information Theory, Vol. 47, No. 2, February 2001, pp. 619-637.